//
//  Problem31.swift
//  TestProject 31. 下一个排列
//
//  Created by 武侠 on 2020/8/20.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit
/*
 31. 下一个排列 --》比这个排列刚刚大
 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

 必须原地修改，只允许使用额外常数空间。

 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 1,2,3 → 1,3,2
 3,2,1 → 1,2,3
 1,1,5 → 1,5,1
 */
@objcMembers class Problem31: NSObject {
    @objc func solution() {
        var list:[Int] = [1, 2, 3]
        nextPermutation(&list)
        print(list)
        
        var list1:[Int] = [3,2,1]
        nextPermutation(&list1)
        print(list1)
        
        var list2:[Int] = [1,1,5]
        nextPermutation(&list2)
        print(list2)
    }
    
    // 算法：
    // 1: 从右至左，找是一个不是升序的数字，
    //    例子：3 6 4 1， 找到了3，因为升序6 4 1已经是最大了，无论怎么改变都不会变的再大，所以需要找 3
    // 2: 找到升序队列里面，刚刚比3大的那个数字4，他们交换 这样才会刚刚大
    // 3: 把后面的对接从左->右升序
    func nextPermutation(_ nums: inout [Int]) {
        if nums.count <= 1 {
            return
        }
        
        // 1: 从右至左，找是一个不是升序的数字，
        var i = nums.count - 2
        var j = nums.count - 1
        while j > 0 {
            if nums[i] < nums[j] {
                break
            }
            i -= 1
            j -= 1
        }
        
        if i >= 0 {
            // 2: 找到升序队列里面，刚刚比3大的那个数字4，他们交换
            var n = nums.count - 1
            while n > i {
                if nums[n] > nums[i] {
                    break
                }
                n -= 1
            }
            
            // 交换
            let temp = nums[n]
            nums[n] = nums[i]
            nums[i] = temp
        }
//        print(nums)
        
        // 3: 把后面的对接从左->右升序
        i = j
        j = nums.count - 1
        while i < j {
            let temp = nums[j]
            nums[j] = nums[i]
            nums[i] = temp
            i += 1
            j -= 1
        }
    }
}
